package leetcode.editor.cn;
//n 位格雷码序列 是一个由 2ⁿ 个整数组成的序列，其中：
//
// 
// 每个整数都在范围 [0, 2ⁿ - 1] 内（含 0 和 2ⁿ - 1） 
// 第一个整数是 0 
// 一个整数在序列中出现 不超过一次 
// 每对 相邻 整数的二进制表示 恰好一位不同 ，且 
// 第一个 和 最后一个 整数的二进制表示 恰好一位不同 
// 
//
// 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2
//输出：[0,1,3,2]
//解释：
//[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
//- 00 和 01 有一位不同
//- 01 和 11 有一位不同
//- 11 和 10 有一位不同
//- 10 和 00 有一位不同
//[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
//- 00 和 10 有一位不同
//- 10 和 11 有一位不同
//- 11 和 01 有一位不同
//- 01 和 00 有一位不同
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[0,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 16 
// 
//
// Related Topics 位运算 数学 回溯 👍 658 👎 0


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution259 {

    /**
     * 格雷码也可以使用公式直接求出。第 i (i≥0)i~(i \geq 0)i (i≥0) 个格雷码即为：
     *
     * gi=i⊕⌊i2⌋g_i = i \oplus \lfloor \frac{i}{2} \rfloor
     * g
     * i
     * ​
     *  =i⊕⌊
     * 2
     * i
     * ​
     *  ⌋
     * 其中 ⊕\oplus⊕ 表示按位异或运算。其正确性证明如下：
     *
     * 当 iii 为偶数时，iii 和 i+1i+1i+1 只有最低的一个二进制位不同，而 ⌊i2⌋\lfloor \dfrac{i}{2} \rfloor⌊
     * 2
     * i
     * ​
     *  ⌋ 和 ⌊i+12⌋\lfloor \dfrac{i+1}{2} \rfloor⌊
     * 2
     * i+1
     * ​
     *  ⌋ 相等，因此 gig_ig
     * i
     * ​
     *   和 gi+1g_{i+1}g
     * i+1
     * ​
     *   也只有最低的一个二进制位不同；
     *
     * 当 iii 为奇数时，我们记 iii 的二进制表示为 (⋯01⋯11)2(\cdots01\cdots11)_2(⋯01⋯11)
     * 2
     * ​
     *  ，i+1i+1i+1 的二进制表示为 (⋯10⋯00)2(\cdots10\cdots00)_2(⋯10⋯00)
     * 2
     * ​
     *  ，即：
     *
     * iii 和 i+1i+1i+1 的二进制表示的若干个最高位是相同的；
     *
     * iii 和 i+1i+1i+1 的二进制表示从高到低的第一个不同的二进制位，iii 中的二进制位为 000，而 i+1i+1i+1 中的二进制位为 111。在这之后，iii 的所有二进制位均为 111，i+1i+1i+1 的所有二进制位均为 000。
     *
     * 那么，⌊i2⌋\lfloor \dfrac{i}{2} \rfloor⌊
     * 2
     * i
     * ​
     *  ⌋ 和 ⌊i+12⌋\lfloor \dfrac{i+1}{2} \rfloor⌊
     * 2
     * i+1
     * ​
     *  ⌋ 的二进制表示分别为 (⋯01⋯1)2(\cdots01\cdots1)_2(⋯01⋯1)
     * 2
     * ​
     *   和 (⋯10⋯0)2(\cdots10\cdots0)_2(⋯10⋯0)
     * 2
     * ​
     *  。因此有：
     *
     * gi=(⋯01⋯11)2⊕(⋯01⋯1)2=(⋯010⋯0)2g_i = (\cdots01\cdots11)_2 \oplus (\cdots01\cdots1)_2 = (\cdots010\cdots0)_2
     * g
     * i
     * ​
     *  =(⋯01⋯11)
     * 2
     * ​
     *  ⊕(⋯01⋯1)
     * 2
     * ​
     *  =(⋯010⋯0)
     * 2
     * ​
     *
     * 以及：
     *
     * gi+1=(⋯10⋯00)2⊕(⋯10⋯0)2=(⋯110⋯0)2g_{i+1} = (\cdots10\cdots00)_2 \oplus (\cdots10\cdots0)_2 = (\cdots 110\cdots0)_2
     * g
     * i+1
     * ​
     *  =(⋯10⋯00)
     * 2
     * ​
     *  ⊕(⋯10⋯0)
     * 2
     * ​
     *  =(⋯110⋯0)
     * 2
     * ​
     *
     * 也只有一个二进制位不同。
     *
     * 注意到，当我们在表示 i+1i+1i+1 时，使用的的是 (⋯10⋯00)2(\cdots10\cdots00)_2(⋯10⋯00)
     * 2
     * ​
     *  ，默认了其二进制表示的低位至少有两个 000。事实上，当 i+1i+1i+1 是 222 的倍数而不是 444 的倍数时，结论是相同的。读者可以自行推导这种特殊情况。
     *
     * @param n
     * @return
     */
    public List<Integer> grayCode(int n) {
        List<Integer> gray = new ArrayList<Integer>();
        for(int binary = 0;binary < 1 << n; binary++){
            gray.add(binary ^ binary >> 1);
        }
        return gray;
    }

    public List<Integer> grayCode3(int n) {
        List<Integer> gray = new ArrayList<Integer>();
        gray.add(0); //初始化 n = 0 的解
        for (int i = 0; i < n; i++) {
            int add = 1 << i; //要加的数
            //倒序遍历，并且加上一个值添加到结果中
            for (int j = gray.size() - 1; j >= 0; j--) {
                gray.add(gray.get(j) + add);
            }
        }
        return gray;
    }

    public List<Integer> grayCode2(int n) {
        LinkedList<Integer> result = new LinkedList<>();
        result.add(0);
        int totalSize = 1 << n;
        int last;
        while (result.size() < totalSize) {
            last = result.getLast();
            for (int i = 1; i <= n; i++) {
                int next = getNext(i, last);
                if (!result.contains(next) && next < totalSize) {
                    result.add(next);
                    break;
                }
            }
        }
        return result;
    }

    LinkedList<Integer> res = new LinkedList<>();
    int n = 0;
    int total = 0;

    public List<Integer> grayCode1(int n) {
        res.add(0);
        this.n = n;
        total = 1 << n;
        bfs();
        return res;
    }

    private void bfs() {
        if (total == res.size()) {
            return;
        }
        for (int i = 1; i <= n; i++) {
            int next = getNext(i, res.getLast());
            if (!res.contains(next) && next < total) {
                res.add(next);
                bfs();
            }
        }
    }

    /**
     * 移动一个数值之后的数
     *
     * @param i    移动第几位
     * @param last 将该数字
     * @return 移动之后的数
     */
    private int getNext(int i, Integer last) {
        String binaryString = Integer.toBinaryString(last);
        int length = binaryString.length();
        if (i <= length && binaryString.charAt(length - i) == '1') return last ^ (1 << (i - 1));
        return last | (1 << (i - 1));
//        if (i > length) {
//            return last | (1 << (i - 1));
//        } else {
//            int j = binaryString.charAt(length - i) - '0';
//            if (j == 0) {
//                return last | (1 << (i - 1));
//            } else {
//                return last ^ (1 << (i - 1));
//            }
//        }

    }

    public static void main(String[] args) {
        Solution259 s = new Solution259();
        System.out.println(s.grayCode(16));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
